package lcr;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

public class Test0030 {
}

class Solution0030_1 {
    class RandomizedSet {

        List<Integer> list=new ArrayList<>();
        Map<Integer,Integer> map=new HashMap<>();
        Random rand=new Random();

        /** Initialize your data structure here. */
        public RandomizedSet() {

        }

        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            if (map.containsKey(val)) return false;

            map.put(val,list.size());
            list.add(val);

            return true;
        }

        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            if (!map.containsKey(val)) return false;
            Integer fina = list.get(list.size());
            Integer index = map.get(val);

            list.set(index,fina);
            list.remove(list.size());
            map.put(fina, index);
            map.remove(val);
            return true;
        }

        /** Get a random element from the set. */
        public int getRandom() {
            int i = rand.nextInt(list.size());
            return list.get(i);
        }
    }
}


